package org.bear.graph.base;

import java.util.*;

public class CanFinish2 {
    private Map<Integer, Set<Integer>> edges = new HashMap<>();
    private IndegreeNode[] indegreeArray;

    TreeMap<IndegreeNode, Integer> indegreeMap = new TreeMap<>((a, b)-> {
        if (a.indegree != b.indegree) {
            return a.indegree - b.indegree;
        }
        return a.vertex - b.vertex;
    });

    private static class IndegreeNode {
        int vertex;
        int indegree = 0;
        IndegreeNode(int vertex, int indegree){
            this.vertex = vertex;
            this.indegree = indegree;
        }
    }

    public boolean canFinish(int numCourses, int[][] prerequisites){
        indegreeArray = new IndegreeNode[numCourses];
        for(int i=0; i<numCourses; i++) {
            edges.put(i, new HashSet<>());
            indegreeArray[i] = new IndegreeNode(i, 0);
        }
        for(int i=0;i<prerequisites.length;i++){
            edges.get(prerequisites[i][1]).add(prerequisites[i][0]);
            indegreeArray[prerequisites[i][0]].indegree++;
        }

        for(int i=0; i<numCourses; i++){
            Set<Integer> set = edges.get(indegreeArray[i].vertex);
            if (!set.isEmpty()){
                indegreeMap.put(indegreeArray[i], 0);
            }
        }

        while (!indegreeMap.isEmpty() && indegreeMap.firstKey().indegree==0){
            Map.Entry<IndegreeNode, Integer> entry = indegreeMap.pollFirstEntry();
            Set<Integer> toVertexSet = edges.get(entry.getKey().vertex);
            for(int toVertex : toVertexSet){
                if (indegreeMap.containsKey(indegreeArray[toVertex])){
                    indegreeMap.remove(indegreeArray[toVertex]);
                    indegreeArray[toVertex].indegree--;
                    indegreeMap.put(indegreeArray[toVertex], 0);
                }
            }
        }

        if (indegreeMap.isEmpty()){
            return true;
        }else {
            return false;
        }

    }

    public static void main(String[] args) {
        long t =  System.currentTimeMillis();
        CanFinish2 canFinish2 = new CanFinish2();
        boolean b = canFinish2.canFinish(8, new int[][]{{1,0},{2,6},{1,7},{6,4},{7,0},{0,5}});
        System.out.println(System.currentTimeMillis()-t);
    }
}
